PHP - Validar campos solo con PHP

Hola a todos, tengo el siguiente formulario de envio de emil, necesito validar que todos los campos sean ingresados antes de enviarlo, osea validar solo con PHP que los campos no esten vacios.
Aca les dejo el codigo, dunciona y envia el correo, ojala puedan ayudarme, desde ya muchas gracias
----
<?
if ($_GET['op']!="ok"){
if (isset($_POST['txt_nombre'])){
$mensaje="
Nombre=".$_POST['txt_nombre']."
Direccion=".$_POST['txt_direccion']."
Telefono=".$_POST['txt_telefono']."
Email=".$_POST['txt_mail']."
Comentario=".$_POST['txt_comentario']."";
mail("[email protected]","Comentarios pagina web",$mensaje);
?>
<link href="../css/bmges.css" rel="stylesheet" type="text/css" />
<style type="text/css">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<!--DWLayoutTable
<tr>
<td WIDTH="100%" HEIGHT=26 valign="TOP" background="images/tanewstop.jpg" class="txttit" >
<div style="padding-left:21px;padding-top:7px"><font class="txt49"><strong>CLIENTES...</strong></font></div>
</td>
</tr>-->
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td><div align="center"><img src="images/indicator_amarillo.gif" width="50" height="50" /></div></td>
</tr>
<tr>
<td><div align="center" class="txttit">Enviando correo .<br />
Espere un momento. </div></td>
</tr>
</table>
<script>
setTimeout("window.location='main.php?mod=contacto&op=ok'", 1000);
</script>
<?
}else{
?>
<form id="form1" name="form1" method="post" action="">
<table width="548" border="0" align="center" cellpadding="0" cellspacing="0">
<!--DWLayoutTable-->
<tr>
<td HEIGHT=28 colspan="2" valign="middle" class="txttit" >  <img src="images/taccontactostop.jpg" width="544" height="26" />
<tr>
<td width="206" HEIGHT=19 >
<td width="342" class="txttit" >Todos los campos son obligatorios
<tr>
<td height="22" align="right" valign="top" class="txttit">Nombre:</td>
<td valign="top" class="txt40"><input name="txt_nombre" type="text" class="Estilo2" id="txt_nombre" /></td>
</tr>
<tr>
<td height="22" align="right" valign="top" class="txttit">Dirección:</td>
<td valign="top" class="txt40"><input name="txt_direccion" type="text" class="Estilo2" id="txt_direccion" /></td>
</tr>
<tr>
<td height="22" align="right" valign="top" class="txttit">Teléfono:</td>
<td valign="top" class="txt40"><input name="txt_telefono" type="text" class="Estilo2" id="txt_telefono" /></td>
</tr>
<tr>
<td height="22" align="right" valign="top" class="txttit">Email:</td>
<td valign="top" class="txt40"><input name="txt_mail" type="text" class="Estilo2" id="txt_mail" /></td>
</tr>
<tr>
<td height="19" align="right" valign="top" class="txttit">Comentarios:</td>
<td rowspan="3" valign="top" class="Estilo2"><textarea name="txt_comentario" cols="50" rows="5" class="Estilo2" id="txt_comentario"></textarea></td>
</tr>
<tr>
<td height="38"> </td>
</tr>
<tr>
<td height="26" valign="top" class="blanconegro"><div align="center"></div></td>
</tr>
<tr>
<td height="32" colspan="2" valign="top" class="blanconegro"><div align="center">
<p>
<input name="image" type="image" src="images/enviar.jpg" alt="Enviar" />
</p>
<p><div style="padding-left:70px;padding-top:11px">
<div align="left"><img src="images/email.jpg" width="99" height="58"><img src="images/telefono.jpg" width="99" height="58" /></div>
</div> </p>
</div></td>
</tr>
</table>
</form>
<?
}
}else{
?>
<br />
<div align="center"> <span class="txttit">Hemos recibido su mensaje.<br />
Nos contactaremos con usted lo antes posible.<br />
Gracias </span></div>
<span class="txt40">
<?
}
?>
</span>

Usa Expresiones Regulares, aqui mismo me pasaron esta pagina para hacer pruebas.

http://gollum.inforg.uniovi.es/aii/valida_regexp.php

Suerte!

No me queda claro.¿?¿?

Estoy tratando de ocupar el:

if (empty($_POST['txt_nombre'])) $error .= "<p class="error">No has introducido p/>"

pero no se donde ubicarlo.

Hi! y porque mejor no validas con javascript? hay bastantes frameworks que ya tienen funciones para validar todo eso, como por ejemplo jquery.